Many computer vision and graphics applications rely on finding minimal cuts in graphs, with many of these graphs having grid-like topologies. Examples of such computer vision and graphics problems include interactive two dimensional (2D)/three dimensional (3D) image and video segmentation, image restoration, painting, image fusion and re-targeting, texture synthesis, shape fitting, and 3D surface reconstruction.
One traditional approach of finding the minimum cut in a graph is the maximum flow/minimum cut algorithm by Boykov and Kolmogorov. The Boykov-Kolmogorov algorithm (BK algorithm) is in turn based on the Ford-Fulkerson algorithm, which repeats the process of finding and augmenting paths with non-zero residual capacities until no more paths remain. An added value of the BK algorithm as compared to the Ford-Fulkerson algorithm is the usage of two concurrent search trees together with a tree-reuse strategy to avoid loss of information gained during previous augmentations.
However, existing implementations of the BK algorithm pose significant challenges for application developers and interactive systems. For example, existing implementations of the BK algorithm are geared toward general graphs. This results in poor performance on grid-like graphs, since the memory bandwidth required when accessing the data structures necessary to represent general graphs is often the main bottleneck of the minimum cut computation.
Accordingly, what is needed are systems, methods, and computer program products that reduce the time needed to obtain a minimum cut in a grid-like graph by utilizing graph's regular structure to optimize the computation of the cut.